/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
	#ifdef DEBUG_TREE
	cerr << "new tree created" << endl;
	#endif
	
    rootPid = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{

	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::open" << endl;
	#endif
	
	char buffer[PageFile::PAGE_SIZE];
	
	RC retval = this->pf.open(indexname, mode); if(retval != 0) return retval;
	
	// If pagefile is not empty, read its rootPid info
	if (pf.endPid() > 0) {
		retval = pf.read(0, buffer); if(retval!=0)return retval;
		
		this->rootPid = *((int*)buffer);
	}
	// If the pagefile is empty and was opened in write mode, initialize
	if (pf.endPid() == 0 && mode == 'w') {
		this->rootPid = -1;
		*((int*)buffer) = -1;
		retval = pf.write(0,buffer); if(retval!=0)return retval;
	}
	
	return retval;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    return this->pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::insert: key=" << key << endl;
	#endif
	
	RC rv = 0;
	char buffer[PageFile::PAGE_SIZE];
	
	// If rootPid is -1, we must create root and initialize it
	if (this->rootPid == -1) {
	
		BTLeafNode root;
		PageId newpid = pf.endPid();
		rv = root.insert(key, rid); if(rv!=0)return rv;
		this->rootPid = newpid;
		
		rv = root.write(newpid, pf); if(rv!=0) return rv;
		
		#ifdef DEBUG_TREE
		cerr << "BTreeIndex::insert: initialized root with leaf " << newpid << endl;
		#endif
		
		return 0;
	}
	
	// Call the recursive insertion function
	IndexCursor cursor;
	cursor.pid = rootPid;
	bool dummy = false;
	int dummy1 = 0;
	PageId dummy2 = 0;
	cursor.eid = 0;
	rv = this->recinsert(key, rid, rootPid, dummy1, dummy2, dummy);
	
    return 0;
}

RC BTreeIndex::recinsert(int key, const RecordId &rid, 
                           PageId page, int& ofkey, PageId& ofpid, bool& of)
{
	char buffer[PageFile::PAGE_SIZE];
	char treeinfo_buffer[PageFile::PAGE_SIZE];
	RC rv = 0;
	
	// Load the node
	pf.read(page, buffer);
	pf.read(0, treeinfo_buffer);
	
	/************************* LEAF *********************************/
	if (*((int*)(buffer+LEAF_FLAG)) == IS_LEAF) {
		#ifdef DEBUG_TREE
		cerr << "recinsert: LEAF" << endl;
		#endif
		BTLeafNode node;
		rv = node.read(page, pf); if (rv != 0) return rv;
		
		// No overflow **************************
		if (node.getKeyCount() < MAX_LEAF_KEYS-1) {
			rv = node.insert(key,rid); if (rv != 0) return rv;
			rv = node.write(page,pf); if (rv != 0) return rv;
			of = false;
			#ifdef DEBUG_TREE
			cerr << "recinsert: LEAF no overflow; inserted " << key;
			cerr << " at page" << page << endl;;
			#endif
			return 0;
		
		// Leaf overflow ************************
		} else {
			BTLeafNode sibling;
			BTNonLeafNode newroot;
			int sibkey;
			PageId sibpid = pf.endPid();
			rv = node.insertAndSplit(key,rid,sibling,sibkey); if(rv!=0)return rv;
			rv = node.setNextNodePtr(sibpid); if(rv!=0)return rv;
			rv = node.write(page,pf); if(rv!=0)return rv;
			rv = sibling.write(sibpid,pf); if(rv!=0)return rv;
			if (page == this->rootPid) {
				PageId newrootpid = pf.endPid();
				newroot.initializeRoot(page, sibkey, sibpid);
				rv = newroot.write(newrootpid, pf); if(rv!=0)return rv;
				this->rootPid = newrootpid;
				*((int*)treeinfo_buffer) = newrootpid;
				rv = pf.write(0, treeinfo_buffer); if(rv!=0)return rv;
				
				#ifdef DEBUG_TREE
				cerr << "BTreeIndex::recinsert: new root from leaf" << newrootpid << endl;
				#endif
			}
			ofkey = sibkey;
			ofpid = sibpid;
			of = true;
			#ifdef DEBUG_TREE
			cerr << "BTreeIndex::recinsert: leaf overflow and split" << sibpid << endl;
			#endif
			#ifdef DEBUG_TREE
			cerr << "recinsert: LEAF overflow; insertAndSplitted " << key;
			cerr << " at page" << page << endl;;
			#endif
			return 0;
		}
	}
	/************************ NON-LEAF *******************************/
	else {
		BTNonLeafNode node;
		rv = node.read(page, pf); if(rv!=0)return rv;
		PageId childPid = 0;
		bool childOverflow = false;
		int newchildkey = 0;
		PageId newchildpid = 0;
		
		// Find the child pointer to follow
		rv = node.locateChildPtr(key, childPid); if(rv!=0)return rv;
		
		// Recursively insert key into child
		rv = recinsert(key,rid,childPid,newchildkey,newchildpid, childOverflow);
		 if(rv!=0)return rv;
		
		// No child overflow **************************
		if (childOverflow == false) {
			// No need to insert anything to current node
			of = false;
			return 0;
		}
		// Child overflow *****************************
		else {
			// No non-leaf overflow at current node **********
			if (node.getKeyCount() < MAX_NONLEAF_KEYS-1) {
				rv = node.insert(newchildkey, newchildpid); if(rv!=0)return rv;
				rv = node.write(page,pf); if(rv!=0)return rv;
				of = false;
				return 0;
			}
			// Non-leaf overflow at current node *************
			else {
				BTNonLeafNode sibling;
				BTNonLeafNode newroot;
				int sibkey = 0;
				PageId sibpid = pf.endPid();
				rv = node.insertAndSplit(newchildkey, newchildpid, sibling, sibkey);
				 if(rv!=0)return rv;
				rv = node.write(page,pf); if(rv!=0)return rv;
				rv = sibling.write(sibpid,pf); if(rv!=0)return rv;
				if (page == this->rootPid) {
					PageId newrootpid = pf.endPid();
					newroot.initializeRoot(page, sibkey, sibpid);
					rv = newroot.write(newrootpid, pf); if(rv!=0)return rv;
					this->rootPid = newrootpid;
					*((int*)treeinfo_buffer) = newrootpid;
					rv = pf.write(0, treeinfo_buffer); if(rv!=0)return rv;
					#ifdef DEBUG_TREE
					cerr << "BTreeIndex::recinsert: new root from nonleaf" << endl;
					#endif
				}
				ofkey = sibkey;
				ofpid = sibpid;
				of = true;
				#ifdef DEBUG_TREE
				cerr << "BTreeIndex::recinsert: nonleaf overflow and split" << sibpid << endl;
				#endif
				return 0;
			}
		}
	}
	
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::locate" << endl;
	#endif
	
	RC rv = 0;
	char buffer[PageFile::PAGE_SIZE];
	PageId page = rootPid;
	bool isLeaf = false;
	int eid;
	
	// Iterate until hitting the leaf
	while ( isLeaf == false ) {
		#ifdef DEBUG_TREE
		cerr << "BTreeIndex::locate: page = " << page << endl;
		#endif
		
		BTNonLeafNode node;
		node.read(page,pf);
		if ( node.isNotLeaf() == false ) {
			isLeaf = true;
		} else {
			rv = node.locateChildPtr(searchKey,page); if(rv!=0)return rv;
		}
	}
	
	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::locate: found leaf node at page " << page << endl;
	#endif
	
	BTLeafNode leaf;
	rv = leaf.read(page,pf); if(rv!=0) {cerr << rv << endl; return rv;}
	rv = leaf.locate(searchKey,eid); if(rv!=0)return rv;
	
	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::locate: read and located leaf node: ";
	cerr << "(" << page << ", " << eid << ")" << endl;
	#endif
	
	cursor.pid = page;
	cursor.eid = eid;

    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	RC rv = 0;
	int nkeys;
	BTLeafNode leaf;

	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::readForward: cursor (" << cursor.pid << ", " << cursor.eid << ")" << endl;
	#endif
	
	rv = leaf.read(cursor.pid, pf); if(rv!=0)return rv;
	nkeys = leaf.getKeyCount();

	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::readForward: nkeys=" << nkeys << endl;
	#endif
	
	if (cursor.eid >= nkeys) return RC_INVALID_CURSOR;
	
	// Read the entry
	rv = leaf.readEntry(cursor.eid, key, rid); if(rv!=0)return rv;
	
	// Increment cursor
	cursor.eid++;
	if (cursor.eid >= nkeys) {
		cursor.eid = 0;
		cursor.pid = leaf.getNextNodePtr();
	}
	
	#ifdef DEBUG_TREE
	cerr << "BTreeIndex::readForward output: ";
	cerr << "(" << key << ", " << rid.pid << ", " << rid.sid << ")" << endl;
	#endif
	
    return 0;
}
